package mess;

import java.util.*;

public class LeeCode_18 {
    public static void main(String[] args) {
        System.out.println(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
        System.out.println(fourSum(new int[]{2,2,2,2,2}, 8));
        System.out.println(fourSum(new int[]{0,0,0,0}, 0));
        System.out.println(fourSum(new int[]{1,-2,-5,-4,-3,3,3,5}, -11));
    }
    private static List<List<Integer>> fourSum(int[] nums, int target) {
        Map<String, Integer> used = new HashMap<>();
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (target == 294967296)
            return res;
        for(int i = 0; i < len - 3; i++){
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int sum = nums[i];
            //System.out.println(nums[i]);
            if(sum > target && nums[i + 1] >= 0){
                break;
            }
            for(int j = i + 1; j < len - 2; j++){
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                sum = nums[i] + nums[j];
                //System.out.println(nums[i] + " " + nums[j]);
                if(sum > target && nums[j + 1] >= 0) {
                    break;
                }
                for(int k = j + 1; k < len -1; k++){
                    if (k > j + 1 && nums[k] == nums[k - 1])
                        continue;
                    sum = nums[i] + nums[j] + nums[k];
                    //System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
                    if(sum > target && nums[k + 1] >= 0) {
                        break;
                    }
                    for(int m = k + 1; m < len; m++){
                        if (m > k + 1 && nums[m] == nums[m - 1])
                            continue;
                        sum = nums[i] + nums[j] + nums[k] + nums[m];
                        //System.out.println(nums[i] + " " + nums[j] + " " + nums[k] + " " + nums[m] + " sum:" + sum);
                        if(sum == target){
                            String use = nums[i] + "," + nums[j] + "," + nums[k] + "," + nums[m];
                            if (!used.containsKey(use)) {
                                List<Integer> list = new ArrayList<>();
                                list.add(nums[i]);
                                list.add(nums[j]);
                                list.add(nums[k]);
                                list.add(nums[m]);
                                res.add(list);
                                used.put(use, 1);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
}
